1. Field of the Invention
The present invention relates to methods and apparatuses for performing a modular multiplication and, for example, to the modular multiplication for elliptic curves over GF(2n).
2. Description of the Related Art
Cryptography is one of the essential applications for modular arithmetic. Depending on the form of the modulus N two cryptography methods are basically distinguished. If the modulus is an integer, we speak of a Z/NZ arithmetic. The parameter N stands for a prime number or for composed prime numbers. The parameter Z stands for integers. The RSA equation is an example of the case in which the modulus is composed of two prime numbers:C=MEmod(N).
As is known, C is an encrypted message, M is an un-encrypted or plain message, E is the public key and N is the modulus.
In contrast, the GF(2n) arithmetic is characterised in that the modulus N(x) is a polynomial of a variable x. The polynomial includes a sum of individual powers of x, a coefficient being associated with each power of x. The exponent of the highest power of x is called the degree of the polynomial. If the coefficients are from the field of GF(2), we speak of a GF(2n) modulus or, more generally, of a GF(2n) arithmetic, respectively. The GF(2n) arithmetic is, for example, used in the cryptography of elliptic curves.
A polynomial f(x) ε GF(2) [x] of the degree n−1 is given by the n coefficients an−1, . . . , a0, wherein the ais must be from the set of GF(2) and wherein an−1 per definition is 1:f(x)=1*xn-1+an-2*xn−2+ . . . +a1*x1+a0*x0
The field of GF(2n) is given by an irreducible polynomial of the degree n and by polynomials of GF(2n) of the degree smaller than or equal to n−1.
The addition, in GF(2n), of two elements, that is polynomials, is given by XORing their coefficient vectors with a length of n.
The multiplication, in GF(2n), of two elements, that is polynomials, is obtained by multiplying the polynomials over GF(2n) and subsequently reducing the obtained product modulo the irreducible polynomial N(x) of the degree n, which defines the corresponding field.
Thus, the product polynomial, that is the polynomial which results from the multiplication of a first polynomial f(x) by a second polynomial g(x), must be subjected to a polynomial division with the modulus polynomial N(x) as the divisor to perform the modular operation. The result of f(x)*g(x)modN(x) is the remainder polynomial resulting from the polynomial division.
Before different manners for efficiently performing the modular multiplication over both Z/NZ and GF(2n) are dealt with, it should be noted that the modular exponentiation with both Z/NZ and GF(2n) can be split into a multiplication by means of the well-known Square and Multiply Algorithm. Thus, the following equation is to be solved:C(x)=(M(x))EmodN(x).
The Square and Multiply Algorithm is based on the fact that the exponent E is split into a sum of powers of two:   E  =            ∑      i        ⁢                  E        ⁡                  [          i          ]                    *              2        i            
The following example is to illustrate this. In binary representation, the following is to apply:E=1011.
Thus, the following relation applies:C(x)=M(x)^(1*23+0*22+1*21+1*20)modN(x).
Thus, the following applies:C(x)=(M(x))8*(M(x))0*(M(x))2*(M(x))0modN(x).
For the Z/NZ arithmetic the equations described above are accordingly, with the difference that, instead of M(x), M must be written and, instead of N(x), N must be written.
In the art a well-known efficient and frequently used possibility to calculate the modular multiplications is known as the Montgomery multiplication and, for example, described in “Handbook of Applied Cryptography”, Menezes, van Oorschot, Vanstone, CRC Press, pages 600 to 603. The Montgomery reduction is a technique allowing an efficient implementation of the modular multiplication without the classic modular reduction step being explicitly carried out. Generally in the Montgomery reduction the division operation is expressed by simple shift operations.
Meanwhile, an extension of the Montgomery multiplication operation to the finite field of GF(2n) is also known. This extension is described in “Montgomery multiplication in GF(2k)”, Koc, Azar, Designs, Codes and Cryptography, Vol. 14, 1998, pages 57 to 69. This extension is also described in “A Scalable and Unified Multiplier Architecture for Finite Fields Z/NZ and GF(2n)”, Erkay Savas, et al., Cryptographic Hardware and Embedded Systems (CHESS 2000), pages 281 to 289, Springer Lecture Notes.
It is a disadvantage of the Montgomery multiplication over Z/NZ or GF(2n) that, even if the division operation, which is difficult to implement in hardware, for a modular reduction is bypassed by shift operations, no look-ahead methods are used to accelerate the modular multiplication operation in hardware.
DE 3631992 C2 discloses a method in which the modular multiplication over Z/NZ can be accelerated using a multiplication look-ahead method and using a reduction look-ahead method. The method described in DE 3631992 C2 is also called ZDN method and described in detail referring to FIG. 9. After a starting step 900 of the algorithm, the global variables M, C and N are initialised. It is the objective to calculate the following modular multiplication:Z=M*CmodN.
M is called the multiplier, C being called the multiplicand. Z is the result of the modular multiplication, N being the modulus.
Then, various local variables, which do not have to be dealt with now, are initialised. Two look-ahead methods are then applied. In the multiplication look-ahead method GEN_MULT_LA, a multiplication shift value sz as well as a multiplication look-ahead parameter a are calculated (910) using various look-ahead rules. The current contents of the Z register is then subjected (920) to a left-shift operation by sz digits.
Essentially parallel to this a reduction look-ahead method GEN_Mod_LA (930) is performed to calculate a reduction shift value sN and a reduction parameter b. In a step 940, the current contents of the modulus register, that is N, is shifted by sN digits to produce a shifted modulus value N′. The central three-operands operation of the ZDN method takes place in a step 950. After step 920 the intermediate result Z′ is added to the multiplicand C which is multiplied by the multiplication look-ahead parameter a and to the shifted modulus N′ which is multiplied by the reduction look-ahead parameter b. According to the current situation, the look-ahead parameters a and b may have a value of +1, 0 or −1.
One case is that the multiplication look-ahead parameter a is +1 and the reduction look-ahead parameter b is −1 so that the multiplicand C is added to a shifted intermediate result Z′ and the shifted modulus N′ is subtracted therefrom. Among others, a could have a value of 0 if the multiplication look-ahead method allowed more than one preset number of individual left shifts, that is, if sz were greater than the maximum allowed value of sz which is also called k. For the case that a equals 0 and that Z′, due to the preceding modular reduction, that is the preceding subtraction of the shifted modulus, is still quite small, and especially smaller than the shifted modulus N′, no reduction needs to take place so that the parameter b equals 0.
The steps 910 to 950 are performed until all the digits of the multiplicand have been processed, that is, until m equals 0 and until a parameter n also equals 0, which indicates whether the shifted modulus N′ is still greater than the original modulus N and whether, despite the fact that all the digits of the multiplicand have already been processed, further reduction steps must be performed by subtracting the modulus from Z.
Finally, it is determined whether Z is smaller than 0. If this is the case, the modulus N must be added to Z to obtain a final reduction so that in the end a positive result Z of the modular multiplication is obtained. In a step 960, the modular multiplication is finished by means of the ZDN method.
The multiplication shift value sz as well as the multiplication parameter a, which are calculated in step 910 by the multiplication look-ahead algorithm, arise from the topology of the multiplier as well as from the inserted look-ahead rules described in DE 3631992 C2.
The reduction shift value sN and the reduction parameter b are determined by comparing the current contents of the Z register with a value of ⅔ times N, as is also described in DE 3631992 C2. It is due to this comparison that the ZDN method has its name (ZDN=Zwei Drittel N=Two Thirds N).
As is illustrated in FIG. 9, the ZDN method reduces the modular multiplication to a three-operands addition (Block 950 in FIG. 9), the multiplication look-ahead method and, therefore, the reduction look-ahead method being utilized to increase the computing time efficiency. Compared to the Montgomery reduction for Z/NZ, a computing time advantage by a factor in the order of magnitude of 3 can thus be obtained.
As has already been explained, the ZDN method described in DE 3631992 C2 only works for the Z/NZ arithmetic. It is, however, not suitable for the GF(2n) arithmetic. Thus, at present, there is no method in which computing time efficient look-ahead methods can be utilized for the GF(2n) arithmetic to accelerate the modular multiplication over GF(2n).